#include<iostream>
#include<fstream>

using namespace std;

long gcd1(long int m,long int n){
	if(m < n)
		return gcd1(n,m);
	return(!n)? m : gcd1(n,m%n);
}

long int gcd2(long int m,long int n){
	if(m < n)
		return gcd2(n,m);
	if(m == 0)
		return n;
	if(n == 0)
		return m;
	return gcd2(m -n,n);
}

long int gcd3(long int m,long int n){
	if(m < n)
		return gcd3(n,m);
	if(n == 0)
		return m;
	if( m % 2 ==0){
		if( n %2 ==0){
			return 2 * gcd3 (m>>1 ,n>>1);
		}else{
			return gcd3(m>>1,n);
		}
	}else{
		if( n % 2  ==0){
			return gcd3(m,n>>1);
		}else
			return gcd3(m-n,n);
	}
}
int main(){
	long int m,n;
	ifstream ifs;
	ifs.open("../data/gcd.dat");
	while(!ifs.eof()){
		ifs >>m >>n;
		if(m < n){
			long temp = m;
			m = n;
			n = temp;
		}
		cout<<"gcd by method 1 :"<<gcd1(m,n)<<endl;
		cout<<"gcd by method 2 :"<<gcd2(m,n)<<endl;
		cout<<"gcd by method 3 :"<<gcd3(m,n)<<endl;
	}
	return 0;
}
